package chapter05_string;

/**
 * 描述：字符串匹配问题
 *      str不包含.和*，exp字符串中.表示匹配任意一个字符，*表示*的前一个字符可以有0个或者任意个
 *
 * @author hl
 * @date 2021/9/28 21:24
 */
public class IsMatch {
    public static void main(String[] args) {
        String str = "abcd";
        String exp = ".*";
        IsMatch main = new IsMatch();
        boolean res = main.isMatch(str, exp);
        System.out.println(res);
        boolean res2 = main.isMatchDP(str, exp);
        System.out.println(res2);
    }


    /**
     * 递归
     * process(s, si, e, ei)的结果表示str[si...str.length-1]是否能被exp[ei...exp.length-1]匹配
     *
     *      分情况讨论：
     *      1）如果已经满足ei == exp.length，并且只需要判断si是否达到了str.length，两个都为""也匹配成功
     *
     *      2）如果e[ei + 1] != '*'，那么此时的s[si] == e[ei]，并且str[si + 1]可以被exp[ei + 1]匹配，才能返回true
     *
     *      3）如果e[ei + 1] == '*'，
     *          3.1那么如果此时s[si] != e[ei]，那么就让*表示*的前一位为0，也就是e[ei] == ‘’，才能继续往下进行匹配
     *          3.2如果s[si] == e[ei]，那么就再看str[si + 1]是否能被exp[ei + 1]匹配？
     *              3.2.1如果能，则返回true
     *              3.2.2如果不能，就假设当前s[si]与e[i]*匹配成功，仅让si++，继续走2)流程
     *
     * @param str
     * @param exp
     * @return
     */
    public boolean isMatch(String str, String exp){
        return isValid(str, exp) && process(str, 0, exp, 0);
    }

    public boolean process(String s, int si, String e, int ei){
        if (ei == e.length()) {
            //1，
            return si == s.length();
        }
        if (ei + 1 == e.length() || e.charAt(ei + 1) != '*') {
            //2
            return si != s.length() && (s.charAt(si) == e.charAt(ei) || e.charAt(ei) == '.')
                    && process(s, si + 1, e, ei + 1);
        }
        while (si != s.length() && (s.charAt(si) == e.charAt(ei) || e.charAt(ei) == '.')){
            //3.2
            if (process(s, si + 1, e, ei + 2)) {
                //3.2.1
                return true;
            }
            //3.2.2
            si++;
        }
        //3.1
        return process(s, si, e, ei + 2);
    }
    
    public boolean isMatchDP(String str, String exp){
        if (!isValid(str, exp)) {
            return false;
        }
        int m = str.length(), n = exp.length();
        //初始化倒数两列和倒数第一行
        boolean[][] dp = initMap(str, exp);
        for (int i = m - 1; i >= 0; i--) {
            for (int j = n - 2; j >= 0; j--) {
                if (exp.charAt(j + 1) != '*') {
                    dp[i][j] = (str.charAt(i) == exp.charAt(j) || exp.charAt(j) == '.') && dp[i + 1][j + 1];
                }else{
                    int si = i;
                    while(si != str.length() && (str.charAt(si) == exp.charAt(j) || exp.charAt(j) == '.')){
                        if (dp[si][j + 2]) {
                            dp[i][j] = true;
                            break;
                        }
                        si++;
                    }
                    if(!dp[i][j]){
                        dp[i][j] = dp[si][j + 2];
                    }
                }
            }
        }
        return dp[0][0];
    }

    private boolean[][] initMap(String str, String exp) {
        int m = str.length(), n = exp.length();
        boolean[][] dp = new boolean[m + 1][n + 1];
        dp[m][n] = true;
        if (m > 0 && n > 0) {
            dp[m - 1][n - 1] = str.charAt(m - 1) == exp.charAt(n - 1) || exp.charAt(n - 1) == '.';
        }
        for (int i = n - 2; i >= 0; i -= 2) {
            if (exp.charAt(i) != '*' && exp.charAt(i + 1) == '*') {
                dp[m][i] = true;
            }else{
                break;
            }
        }
        return dp;
    }

    public boolean isValid(String str, String exp){
        if (str == null || exp == null) {
            return false;
        }
        //str valid
        for (int i = 0; i < str.length(); i++) {
            if (str.charAt(i) == '.' || str.charAt(i) == '*') {
                return false;
            }
        }
        //exp valid
        for (int i = 0; i < exp.length(); i++) {
            if (str.charAt(i) == '*' && (i == 0 || str.charAt(i - 1) == '*')) {
                return false;
            }
        }
        return true;
    }
}
